//题目:
// 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
// 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
// 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
// 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution 
{
public:
    bool isCousins(TreeNode* root, int x, int y) 
    {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            int flag1=false,flag2=false;
            for(int i=0;i<size;i++)
            {
                //同层结点出队列
                TreeNode* node=q.front();
                q.pop();
                
                //子节点入队列
                if(node->left){
                    q.push(node->left);
                    if(node->left->val==x)flag1=true;
                    if(node->left->val==y)flag2=true;
                }
                if(node->right){
                    q.push(node->right);
                    if(node->right->val==x)flag1=true;
                    if(node->right->val==y)flag2=true;
                }

                if(node->left && node->right && ((node->left->val==x && node->right->val==y) || (node->left->val==y && node->right->val==x)))
                {
                    flag1=false;
                    flag2=false;
                }
            }
            if(flag1 && flag2)return true;
        }
        return false;
    }
};